package graph;

/**
 * 使用邻接矩阵来表示图
 */
public class Graph {

    int vertexCount;
    int type;
    //使用邻接矩阵来表示
    int[][] adjMatrix;

    //初始化邻接矩阵
    public Graph(int n, int type) {
        vertexCount = n;
        this.type = type;
        adjMatrix = new int[n][n];
    }

    //判断图的类型
    public int getType() {
        return type;
    }

    //获取图的顶点数
    public int getVertexCount() {
        return vertexCount;
    }

    //获取边的条数
    public int getEdgeCount() {
        int count = 0;
        for (int i = 0; i < vertexCount; i++) {
            for (int j = 0; j < vertexCount; j++) {
                if (adjMatrix[i][j] != 0) {
                    count++;
                }
            }
        }
        //如果是无向图，还要除以2
        if (type == 0) {
            count /= 2;
        }
        return count;
    }

    //序号为u和v的两个点之间插入边
    public void insertEdge(int u, int v) {
        if (type == 0) {
            adjMatrix[u - 1][v - 1] = 1;
            adjMatrix[v - 1][u - 1] = 1;
        } else {
            adjMatrix[u][v] = 1;
        }
    }

    //删除边
    public void deleteEdge(int u, int v) {
        if (type == 0) {
            adjMatrix[u - 1][v - 1] = 0;
            adjMatrix[v - 1][u - 1] = 0;
        } else {
            adjMatrix[u - 1][v - 1] = 0;
        }
    }

    //判断两个顶点是否相连
    public boolean isAdjacent(int u, int v) {
        return adjMatrix[u][v] == 1;
    }

    /**
     * 计算顶点的度
     */
    public int getDegree(int u) {
        int degree = 0;
        if (type == 0) {
            for (int j = 0; j < vertexCount; j++) {
                if (adjMatrix[u - 1][j] != 0) {
                    degree++;
                }
            }
        } else {
            //有向图的度为出度和入度之和
            for (int j = 0; j < vertexCount; j++) {
                if (adjMatrix[u - 1][j] != 0) {
                    degree++;
                }
            }
            for (int i = 0; i < vertexCount; i++) {
                if (adjMatrix[i][u - 1] != 0) {
                    degree++;
                }
            }
        }
        return degree;
    }

    //获取入度
    public int getInDegree(int u) {
        int degree = 0;
        if (type == 0) {
            System.err.println("无向图没有出度和入度");
        } else {
            for (int i = 0; i < vertexCount; i++) {
                if (adjMatrix[i][u - 1] != 0) {
                    degree++;
                }
            }
        }
        return degree;
    }

    //获取出度
    public int getOutDegree(int u) {
        int degree = 0;
        if (type == 0) {
            System.err.println("无向图没有出度和入度");
        } else {
            for (int j = 0; j < vertexCount; j++) {
                if (adjMatrix[u - 1][j] != 0) {
                    degree++;
                }
            }
        }
        return degree;
    }
}
